import java.util.*;

// 7 10
public class DoubleProduction {


    public static void main(String[] args) {
        System.out.println((int)'a');
        System.out.println((int)'z');
        System.out.println((int)'A');
//        System.out.println(Arrays.toString());
        String s = "gghh";
        System.out.println(s.contains("h"));
        CharSequence c = "hhh";
        Map map = new HashMap();

        String[] ss = c.toString().split(" ");


        String s1 = s.substring(0,3);

        System.out.println(s1);

        System.out.println(c);
    }

    /**
     * 最小覆盖子串 diff  
     */

    //我这个计数器count表示是当前符合的字母 还有种写法表示的是符合字母的种类
    public String minWindowBe(String ss, String tt) {
        ss+=" ";

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hashT = new int[128];

        for(char i: t) hashT[i]++;

        System.out.println("hashT= "+Arrays.toString(hashT));

        int[] hashS = new int[128];

        int n = ss.length(), count=0, length=tt.length();
        int min = Integer.MAX_VALUE;
        String ret = "";
        for(int l=0,r=0; r < n-1; r++){
            char cur = s[r];
            int ts = hashT[cur];
            //进窗口 r++
            if(ts > 0){
                int cs = hashS[cur]++;
                if(cs+1<=ts) count++;
            }
            //出窗口 l++
            while(l<r && (hashT[s[l]]==0 || hashS[s[l]] > hashT[s[l]])){
                char out = s[l++];
                int co = hashS[out];
                if(co==0) {
                    continue;
                }
                int co1 = hashT[out];
                if(co<=co1){
                    count--;
                    hashS[out]--;
                    //小优化 这里直接删除重复元素
                    while(hashS[s[l]]==0){
                        System.out.print(" "+s[l]);
                        l++;
                    }
                    break;
                }
                hashS[out]--;
            }
            //修改值
            if(count==length){
                if(min > r-l+1){
                    min = r-l+1;
                    ret = ss.substring(l,r+1);
                }
            }
        }
        return ret;
    }

    //优化 把hash改为数组hash
    public String minWindow(String ss, String tt) {
        ss+=" ";

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        Map<Character,Integer> mapT = new HashMap<>();

        for(char i: t) mapT.put(i,mapT.getOrDefault(i,0)+1);

        System.out.println("mapt = "+ mapT.toString());

        Map<Character,Integer> mapS = new HashMap<>();

        int n = ss.length(), count=0, length=tt.length();
        int min = Integer.MAX_VALUE;
        String ret = "";
        for(int l=0,r=0; r < n-1; r++){
            char cur = s[r];
            int ts = mapT.getOrDefault(cur,0);
            //进窗口 r++
            if(ts > 0){
                int cs = mapS.getOrDefault(cur,0);
                mapS.put(cur,cs+1);
                if(cs+1<=ts) count++;
            }
            //出窗口 l++
            while(l<r && (!mapT.containsKey(s[l]) || mapS.getOrDefault(s[l],0) > mapT.getOrDefault(s[l],0))){
                char out = s[l++];
                int co = mapS.getOrDefault(out,0);
                if(co==0) {
                    continue;
                }
                int co1 = mapT.getOrDefault(out,0);
                //删除的是有效的元素
                if(co<=co1){
                    count--;
                    mapS.put(out,co-1);
                    if(co-1==0) mapS.remove(out);
                    //小优化 这里直接删除重复元素
                    while(mapS.getOrDefault(s[l],0)==0){
                        l++;
                    }
                    break;
                }
                mapS.put(out,co-1);
            }
            //修改值
            if(count==length){
                if(min > r-l+1){
                    min = r-l+1;
                    ret = ss.substring(l,r+1);
                }
            }
        }
        return ret;
    }    /**
     * 串联所有单词的子串 diff
     * 和下面拿到的be解法的算法一致 不过实现使用map 跟复杂
     */
    public List<Integer> findSubstring(String s, String[] words) {
        s+=" ";
        Map<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        int length = words[0].length(), size = words.length;
        int n = s.length(), count = 0;
        List<Integer> ret = new LinkedList<>();

        Hashtable<String, String> h = new Hashtable<>();

        for (int i = 0; i < length; i++) {
            windows(ret, map, i, length, size, n, count, s);
        }
        return ret;
    }

    void windows(List<Integer> ret, Map<String, Integer> map,
                 int i, int length, int size, int n, int count,
                 String s) {
        Map<String, Integer> map2 = new HashMap<>();
        for (int l = i, r = i+length; r < n; r += length) {
            //进窗口
            String str = s.substring(r-length, r);
            int sc = map2.getOrDefault(str, 0);
            map2.put(str, sc + 1);

            if (sc + 1 <= map.getOrDefault(str, 0)) count++;

            //出窗口
            if (r - l > size * length) {
                String out = s.substring(l, l += length);
                int sc2 = map2.get(out);
                if (sc2 <= map.getOrDefault(out,0)) count--;

                map2.put(out, sc2 - 1);

                if (sc2-1 <= 0) {
                    map2.remove(out);
                }
            }
            if (count == size) ret.add(l);
        }
    }

    /**
     * 找到字符串中所有字母异位词
     */
    //使用eff来记录这个窗口中有的有效之母个数 但他们个数给p的长度相同之后就满足了条件
    public List<Integer> findAnagramsBe(String s, String p) {
        char[] p1 = p.toCharArray();

        int[] pc = new int[26], sc = new int[26];
        for(char i : p1) pc[i-'a']++;

        List<Integer> ret = new LinkedList<>();
        int n = p.length();
        char[] s1 = s.toCharArray();

        for(int l = 0, r = 0, effe = 0; r < s.length(); r++){
            //进窗口
            if(++sc[s1[r]-'a']<=pc[s1[r]-'a']) effe++;
            //出窗口 3
            if(r - l + 1 > n){
                char out = s1[l++];
                if(sc[out-'a']-- <= pc[out-'a']) effe--;
            }

            //修改
            if(effe==n) ret.add(l);
        }
        return ret;
    }
    // toCharArray 比charAt快
    public List<Integer> findAnagrams(String s, String p) {
        int n = p.length(), count = 0;
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        int[] pc = new int[26];
        int[] sc = new int[26];
        List<Integer> ret = new LinkedList<>();
        for(int i = 0; i < n;i++) pc[p1[i]-'a']++;
        for(int l = 0, r= 0; r < s.length(); r++){
            //进窗口
            sc[s1[r]-'a']++;
            count++;
            //出窗口
            if(count > n){
                sc[s1[l]-'a']--;
                l++; count--;
            }
            //修改
            if(count==n){
                if(equalArr(sc,pc, n)){
                    ret.add(l);
                }
                sc[s1[l]-'a']--;
                l++; count--;
            }
        }

        return ret;
    }

    boolean equalArr(int[] sc, int[] pc,int n) {
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (sc[i] != pc[i]) {
                return false;
            }

            if (sc[i] != 0) {
                count++;
                if (count > n) {
                    break;
                }
            }
        }
        return true;
    }

    /**
     * 水果成篮
     */

    //这是使用了俩个数来当作哈希
    public int totalFruitBe(int[] fruits) {
        int n = fruits.length, max = 0;
        int a = -1, ac = 0;
        int b = -1, bc = 0;
        for(int l = 0, r = 0; r < n; r++){
            //入窗口 判断水果种类 用俩个参数记录下最近的就好
            if(a == -1  && fruits[r]!=b){
                a = fruits[r];
            }else if(b == -1 && fruits[r]!=a){
                b = fruits[r];
            }
            if(fruits[r] == a) ac++;
            else if(fruits[r] == b) bc++;
            else{
                //出窗口
                while(l<r){
                    if(fruits[l]==a){
                        if(ac == 1){
                            a=fruits[r];
                            l++;
                            break;
                        }
                        ac--;
                    }else{
                        if(bc == 1){
                            b=fruits[r];
                            l++;
                            break;
                        }
                        bc--;
                    }
                    l++;
                }
            }
            max = Math.max(r-l+1,max);
        }
        return max;
    }

    public int totalFruit(int[] fruits) {
        int n = fruits.length, max = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int l = 0, r = 0; r < n; r++){
            //入窗口 判断水果种类 用俩个参数记录下最近的就好
            if(!map.containsKey(fruits[r])){
                map.put(fruits[r],1);
            }else{
                map.put(fruits[r],map.get(fruits[r])+1);
            }
            //出窗口
            while(map.size()>2){
                //等于都要减去在map中 当tmp == 1退出
                int c = map.get(fruits[l]);
                if(c==1){
                    map.remove(fruits[l]);
                    l++;
                    break;
                }
                map.put(fruits[l], c-1);
                l++;
            }

            //这是l指向的时最左边的第二种果子
            max = Math.max(r-l+1,max);
        }
        return max;
    }

    /**
     * 将 x 减到 0 的最小操作数
     */
    public int minOperations(int[] nums, int x) {
        int n = nums.length, sum = 0, max = 0;
        for(int i : nums) sum+=i;
        int target = sum - x;
        if(target < 0) return -1;
        if(target == 0) return n;

        int cur = 0;
        for(int l = 0, r = 0; r < n; r++){
            cur += nums[r];

            // 出窗口
            while(cur > target){
                cur-=nums[l];
                l++;
            }
            if(cur == target)
                max = Math.max(max, r - l +1);
        }
        return max == 0? -1 : n - max;
    }
    /**
     * 最大连 续1的个数 III
     */
    //滑动窗口
    public int longestOnesWindow(int[] nums, int k) {
        //可以转换为 找到最长的1的数组，其中包含k个0
        int n = nums.length,max = k,zero=0;
        if(k >= n){
            return n;
        }
        for(int l=0,r=0;r<n;r++){
            //进窗口
            if(nums[r]==0) zero++;

            //出窗口
            while(zero>k){
                if(nums[l]==0) zero--;
                l++;
            }

            max = Math.max(r-l+1,max);
        }
        return max;
    }
    //枚举
    public int longestOnes(int[] nums, int k) {
        int n = nums.length,max = k;
        //记录反转下标
        Queue<Integer> queue = new LinkedList<>();
        if(k >= n){
            return n;
        }
        int l = k == 0 ? -1:0;
        for(int r = 0; r < n; r++){
            if(nums[r]==1){
                l = l==-1? r:l;
             }else if(nums[r]==0 && k!=0){
                max = Math.max(r-l+1,max);
                queue.add(r);
                k--;
            }else if(nums[r]==0 && k==0 && !queue.isEmpty()){
                l = queue.poll()+1;
                max = Math.max(r-l+1,max);
                queue.add(r);
            }else{
                l = -1;
            }
        }
        return max;
    }

    /**
     * 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[128];
        int min = 0, n = s.length();
        if(n == 0) return 0;
        for(int l = 0, r = 0; r < n; r++){
            hash[s.charAt(r)]++;
            while(hash[s.charAt(r)] > 1){
                hash[s.charAt(l++)]--;
            }

            min = Math.max(min,r - l + 1);
        }
        return min;
    }

    /**
     * 长度最小的子数组
     */
    public int minSubArrayLen(int target, int[] nums) {
        if(nums[0]>=target){
            return 1;
        }
        int l = 0,n = nums.length;
        int cur = nums[0],min = 100_001;
        for(int r = 1; r < n;){
            if(cur < target){
                cur += nums[r];
                // System.out.println("小于target "+ cur);
                r++;
            }
            while(cur >= target){
                // System.out.println("大于target "+ cur);
                min = Math.min(min,r-l);
                cur -= nums[l];
                l++;
            }
        }
        return min == 100_001 ? 0: min;
    }

    /**
     * 四数字和
     */
    public List<List<Integer>> fourSumBe(int[] nums, int target) {
        //排序 先固定一个在固定一个
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = n -1; i >= 3;){
            // System.out.print(i);
            for(int j = i - 1; j >= 2;){
                int l = 0; int r = j - 1;
                long sum =  (long)target -  nums[i] -  nums[j];

                while(r > l){
                    long f =  nums[l] +  nums[r];
                    if(f > sum){
                        r--;
                    }else if(f < sum){
                        l++;
                    }else{
                        ret.add(Arrays.asList(nums[l],nums[r],nums[j],nums[i]));//这里课已使用之前的方法来去重
                        l++;r--;
                        while(l < r && nums[l] == nums[l-1]) l++;
                        while(l < r && nums[r] == nums[r+1]) r--;
                    }
                }
                j--;
                while(j >=2 && nums[j] == nums[j+1]) j--;
            }
            i--;
            while(i >= 3 && nums[i] == nums[i+1]) i--;

        }
        return ret;
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //排序 先固定一个在固定一个
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        for (int i = n - 1; i >= 3; i--) {
            // System.out.print(i);
            for (int j = i - 1; j >= 2; j--) {
                int l = 0;
                int r = j - 1;
                long sum = (long) target - nums[i] - nums[j];

                while (r > l) {
                    long f = nums[l] + nums[r];
                    if (f > sum) {
                        r--;
                    } else if (f < sum) {
                        l++;
                    } else {
                        set.add(Arrays.asList(nums[l], nums[r], nums[j], nums[i]));
                        l++;
                        r--;
                    }
                }
            }
        }
        for (List<Integer> l : set) {
            ret.add(l);
        }
        return ret;
    }
    /**
     * 三数之和
     * 主要时去重
     *   set.add(Arrays.asList(nums[i],nums[left],nums[right])); 可以去重
     *  因为Arrays.asList() 创建的列表实现了基于内容的相等性判断
     */
    int[] paththreeSum;
    List<List<Integer>> retthreeSum;
    int nthreeSum;
    int[] numsthreeSum;
    public List<List<Integer>> threeSumRecursion(int[] _nums) {
        numsthreeSum = _nums;
        nthreeSum = numsthreeSum.length;
        paththreeSum = new int[3];
        retthreeSum = new LinkedList<>();
        Arrays.sort(numsthreeSum);
        recursion(0, 0, 0);
        return retthreeSum;
    }

    void recursion(int level ,int s, int sum){
        if(level == 3){
            if(sum == 0){
                retthreeSum.add(Arrays.asList(paththreeSum[0],paththreeSum[1],paththreeSum[2]));
            }
            return;
        }

        for(int i = s; i < nthreeSum; i++){
            paththreeSum[level] = numsthreeSum[i];
            recursion(level + 1, i + 1, sum + numsthreeSum[i]);
            while(i + 1 < nthreeSum  && numsthreeSum[i + 1] == numsthreeSum[i]) i++;
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = n - 1; i >= 2;){
            if(nums[i]<0){
                return ret;
            }
            int l = 0, r = i - 1;
            while(l < r){
                if(nums[l]+nums[r]+nums[i] > 0){
                    r--;
                }else if(nums[l]+nums[r]+nums[i] < 0){
                    l++;
                }else{
                    ret.add(new ArrayList<>(Arrays.asList(nums[l],nums[r],nums[i])));
                    r--;
                    l++;

                    while(r>l&&nums[r+1]==nums[r])
                        r--;
                    while(r>l&&nums[l-1]==nums[l])
                        l++;
                }
            }
            i--;
            while(i > 0 && nums[i]==nums[i+1]) i--;
        }
        return ret;
    }


    /**
     * 有效三角形的个数
     * 通过排序来覆盖条件
     */
    public int triangleNumber(int[] nums) {
        //排序 情况覆盖
        sortTriangleNumber(nums);

        int len = nums.length;
        int ret = 0;
        for(int end = len-1; end > 1;end--){
            int l = 0, r = end -1;
            while(l < r){
                if(nums[l] + nums[r] > nums[end]){
                    ret+=r-l;
                    r--;
                }else{
                    l++;
                }
            }
        }
        return ret;
    }
    void sortTriangleNumber(int[] nums){
        int len = nums.length;
        for(int i = 0;i < len;i++){
            for(int j = i+1;j< len;j++){
                if(nums[i]>nums[j]){
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
    }
    /**
     * 盛最多水的容器
     */
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1,max = -1;
        while(l != r){
            int v = Math.min(height[l],height[r]) * (r-l);
            max = Math.max(v,max);
            if(height[l]>height[r]){
                r--;
            }else{
                l++;
            }
        }
        return max;
    }
    /**
     * 快乐数
     */

    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNumIsHappy(n);

        while(slow != fast){
            slow = getNumIsHappy(slow);
            fast = getNumIsHappy(getNumIsHappy(fast));
        }
        return slow == 1;
    }

    Integer getNumIsHappy(int num){
        int sum = 0;
        while(num!=0){
            int n = num %10;
            sum+=n*n;
            num/=10;
        }
        return sum;
    }
    /**
     * 复写零
     */
    public void duplicateZeros(int[] arr) {
        int last = 0;
        int sum = 0;
        int l = arr.length;
        for (int i = 0; i < l; i++) {
            if (arr[i] == 0) {
                sum += 2;
            } else {
                sum += 1;
            }
            if (sum >= l) {
                last = i;
                System.out.print(last);
                break;
            }
        }
        moveDuplicateZeros(arr, last, sum);

    }

    void moveDuplicateZeros(int[] arr, int s, int sum) {
        int l = arr.length;
        int des = l - 1;
        if (arr[s] == 0 && sum > l) {
            s--;
            arr[des--] = 0;
        }
        for (int i = s; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[des] = 0;
                des--;
                arr[des] = 0;
                des--;
            } else {
                arr[des] = arr[i];
                des--;
            }
        }
    }

    /**
     * 移动0
     */
    public void moveZeroes(int[] nums) {
        int length = nums.length;
        int i = 0;
        for (int j = 0; i < length;) {
            if (nums[i] != 0) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
                j++;
            }
            i++;

        }
    }

}
